package com.lc.hot100.lc279;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
	}
}

class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        queue.offer(0);
        set.add(0);
        int level = 0;
        while(!queue.isEmpty()) {
        	level ++;
        	int sez = queue.size();
        	for (int i = 0; i < sez; i ++) {
        		int e = queue.poll();
        		for (int j = 1; j <= n; j ++) {
        			
        			int val = e + j * j;
        			if (val > n) {
        				break;
        			}
        			if (val == n) {
        				return level;
        			}
        			if (!set.contains(val)) {
            			queue.offer(val);
            			set.add(val);
        			}
        		}
        		
        	}

        }
        return level;
    }
}
